#include<iostream>
#include<math.h>
#include "stopwatch.cpp"


class Player
{
	public:
	int amount;  
	int ct;
	Player()
	{
		amount=0;
		ct=0;
	}
	int giveMoney()
	{
		if(amount==0) return -1; 
		int current=int(pow(2,ct));
		if(current>amount)
		{
			int temp=amount;
			amount=0;
			return temp;
		}
		else
		{
			amount=amount-current;
			ct++;
			return current; 
		}
	}
	int takeMoney(int money)
	{
		if(amount==0) return -1; 
		amount+=money; 
	}
};

struct PlayerLinkedList
{
	int id;
	Player p;
	PlayerLinkedList *next;
};

int getLinkedListCount(PlayerLinkedList *root)
{
	PlayerLinkedList *temp=root;
	int i=0;
	int startId=root->id;
	while(temp->next->id!=startId)
	{
		temp=temp->next;
		i++;
	}
	return i;
}

PlayerLinkedList* removeNode(PlayerLinkedList *root, PlayerLinkedList *node)
{
	PlayerLinkedList *temp=root;
	int startId=root->id;
	while(1)
	{
		if(temp->next->id==node->id)
		{
			temp->next=temp->next->next;
			break;
		}
		if(temp->next->id==startId)
			break;
		temp=temp->next;
	}
	return (PlayerLinkedList *)temp;
}

PlayerLinkedList* getNode(PlayerLinkedList *root, PlayerLinkedList *node)
{
	PlayerLinkedList *temp=root;
	int startId=root->id;
	while(1)
	{
		if(temp->next->id==node->id)
		{
			return (PlayerLinkedList *)temp->next;
			break;
		}
		if(temp->next->id==startId)
			break;
		temp=temp->next;
	}
	return NULL;

}

void printLinkedList(PlayerLinkedList *root)
{
	PlayerLinkedList *temp=root; 
	int startId=root->id;
	printf("\n*******Final Tally******\n");
	while(temp->next->id!=startId)
	{
		printf("Player %d : %d\n",temp->id,temp->p.amount);		
		temp=temp->next;
	}
}

void playGameLinkedList(int no_of_player, int initial_amt,int gameCnt)
{	gameCnt++;
	//create the circular linked list
	PlayerLinkedList *pListRoot;
	pListRoot=new PlayerLinkedList;
	pListRoot->id=no_of_player-1;
	pListRoot->p.amount=initial_amt;
	pListRoot->next=NULL;
	PlayerLinkedList *pLastNode;
	pLastNode=pListRoot;
	for(int i=no_of_player-2;i>=0;i--)
	{
		PlayerLinkedList *node=new PlayerLinkedList;
		node->id=i;
		node->p.amount=initial_amt;
		node->next=pListRoot;
		pListRoot=node;
	}
	pLastNode->next=pListRoot;

	PlayerLinkedList *currentGiver=pListRoot;
	while(getLinkedListCount(pListRoot)>0)
	{
		int _flag=0;
		PlayerLinkedList *playerTaking=currentGiver;
		//printf("\nCurrent Giver id : %d\t Amount : %d\n",currentGiver->id,currentGiver->p.amount);
		while(currentGiver->p.amount>0)
		{
			playerTaking=playerTaking->next;
			if(playerTaking->id==currentGiver->id)
			{
				_flag=1;
				break;
			}
			int amt=currentGiver->p.giveMoney();
			playerTaking->p.takeMoney(amt);
			//printf("\tPlayer Taking Id : %d\t Taken Amount : %d\t Total Amount left : %d\n",playerTaking->id,amt,playerTaking->p.amount);
		}
		if(_flag) break;
		pListRoot=(PlayerLinkedList *)removeNode(pListRoot,currentGiver);
		currentGiver=(PlayerLinkedList *)getNode(pListRoot,playerTaking);			
	}
	printLinkedList(pListRoot);

}
void playGame(int no_of_player, int initial_amt,int gameCnt)
{
	gameCnt++;
	printf("Result for Game:%d\n",gameCnt);
	printf("\t\t%d Player in this game, $%d per Player \n",no_of_player,initial_amt);

	Player *player;
	player=new Player[no_of_player];
	for(int i=0;i<no_of_player;i++)
		player[i].amount=initial_amt;

	int playersLeft=no_of_player;
	int currentPlayer=0;
	int playerLastRecieved=0;
	int exMon=0;
	int monLeft=0;
	while(playersLeft)
	{
		monLeft=player[currentPlayer].amount;
		int i=(currentPlayer+1)>=no_of_player?0:(currentPlayer+1);
		int _flag=0;
		//printf("Current Player :%d\n",currentPlayer);
		while(player[currentPlayer].amount>0)
		{
			if(i!=currentPlayer)
			{
				if(player[i].amount>0)
				{
					exMon++;
					int amt=player[currentPlayer].giveMoney();
					if(amt==-1) break;

					//printf("\tPlayer %d: %d\n",i,amt); 

					player[i].takeMoney(amt);
					playerLastRecieved=i;
				}
			}
			else
			{
				_flag=1;
				break;
			}
			i++;
			if(i>=no_of_player) i=0;
		}
		if(_flag==1) break;
		currentPlayer=playerLastRecieved;
		playersLeft--;
	}
	printf("\t\t%d Total money exchanges\n",exMon);
	printf("\t\tLast Player to give money : Player %d with $%d remaining\n",(currentPlayer+1),player[currentPlayer].amount);
	printf("\tPlayer remaining:\n");

}

int main()
{
	Stopwatch sw;
	sw.start();
	int gameCnt=0;
//	playGame(1032,200,gameCnt);
	playGameLinkedList(32,2,gameCnt);
	sw.stop();
	double timeTaken=sw.user();
	printf("Time taken : %lf",timeTaken);
	return 0;
	
	
	//playGame(10,10);	
	return 0;
}
